__auth__ = "miao.zhifeng<19195659@qq.com>"
__doc__ = """ 
递归—— 汉诺塔
f(n) 表示当圆盘数量为n时，最少需移动多少次
f(n)的递归公式
 if n==1: f(n) = 1
 if n==2: f(n) = 3
 if n==3: f(n) = 7
 if n==4: f(n) = 15
 so:
 if n=1:  f(n) = 1
 if n>1:  f(n) = 2*f(n-1)+1

 so, 
   f(n) = 2**n+1
"""
import string

# 使用递归定义最少移动次数
# n为待移动的圆盘数
def hano(n):
	if n == 1: 
		return 1
	else:
		return 2*hano(n-1)+1

def hano2(n):
	if n<=0: return 0
	return 2**n-1


# 使用递归定义走法
# n为待移动的圆盘数，
# a - 起点
# b - 终点
# c - 中间借助
def hano_tower(n,a,b,c):
	if n==1:
		print(a+"->"+b)
	else:
		hano_tower(n-1,a,c,b)
		print(a+"->"+b)
		hano_tower(n-1,c,b,a)

# 动态规划出最少次数
def fastHano(n,mem):
	if not n in mem.keys():
		mem[n] = fastHano(n-1,mem)*2+1
	return mem[n]

def HanoDP(n):
	mem = {1:1}
	return fastHano(n,mem)

# 动态规划法找出走法
def fastHT(n,a,b,c,mem):
	if not n in mem.keys():
		item = []		
		item.append(fastHT(n-1,a,c,b,mem))
		item.append(str(a)+"->"+str(b))
		item.append(fastHT(n-1,c,b,a,mem))
		s = ",".join(item)
		mem[n] = s
	return mem[n]
def HTDP(n,a,b,c):
	mem = {1:str(a)+"->"+str(b)}
	return fastHT(n,a,b,c,mem)

n = 5
print(HanoDP(n))
print(hano(n))
print(hano2(n))
hano_tower(n,"A","B","C")
print(HTDP(n,"A","B","C"))